class FeatureSet(list):
    def __init__(self, *args, **kwargs):
        list.__init__(self, *args, **kwargs)
        self.iteration = 0
        
    def update(self, solution, *args, **kwargs):
        """Compute the reward of the given solution and update the values of all features in the 
        feature set accordingly."""
        reward = self.reward(solution, *args, **kwargs)
        for feature in self:
            feature.update(solution, reward)
        self.iteration += 1
        
    def reward(self, solution, value):
        """The simplest reward function just returns the argument value."""
        return value
        
    def value(self, solution):
        """A simple value function, which computes a weighted sum of feature values. 
        NOTE: if the given solution has none of the features in the feature set, i.e. all degrees 
        will be zero, this method will raise an exception because it will try to divide by zero."""
        upper = 0.0
        lower = 0.0
        for feature in self:
            degree = feature.degree(solution)
            upper += degree * feature.value
            lower += degree
        return upper / lower
        
class Feature(object):
    alpha = 0.05 # learning speed parameter (helps determine the weight of new values)
    
    def __init__(self, value=1.0):
        self.value = value
        
    def __cmp__(self, feature):
        return cmp(self.value, feature.value)
        
    def __repr__(self):
        return "<%s(%s) @ 0x%08x>" % (self.__class__.__name__, self.info(), id(self))
        
    def info(self):
        return self.value
        
    def degree(self, solution):
        """This method should return a value between 0 and 1, indicating the degree to which the 
        given solution has this feature."""
        raise NotImplementedError()
        
    def update(self, solution, reward):
        """Update the value of the feature using a simple linear combination which gives weight 
        '1 - degree * alpha' to the previous value and 'degree * alpha' to the given reward."""
        degree = self.degree(solution)
        assert 0.0 <= degree <= 1.0
        self.value = (1.0 - degree * self.alpha) * self.value + degree * self.alpha * reward
        